package 数据结构.栈和队列.Algorithm;

import java.util.*;

/*给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

        有效字符串需满足：

        左括号必须用相同类型的右括号闭合。
        左括号必须以正确的顺序闭合。
        每个右括号都有一个对应的相同类型的左括号。*/
//利用队列：先进先出？ x
//利用栈：先进后出，这样子才能完美包括进去。

//deque模拟栈的实现。

public class isValid {
    public static void main(String[] args) {
        isValid("(){}}{");
    }
    //s:是一个字符串。
    //s 由 [ ( {  } ) ] 组成
    //那么：比如[ 先进去了，那么就代表着 ] 要后出
    public static boolean isValid(String s) {
        Deque<Character>deque=new ArrayDeque<>();
    //得先将字符串分割。
        //要去判断是左括号还是右括号，如果是左则放进去，右则要去判断与栈顶的是否相同
        char c;
        for (int i = 0; i < s.length(); i++) {
        //
            c=s.charAt(i);
            //遇到( 则将 ) 放进栈顶 然后等着去比较
            if(c=='('){
                deque.push(')');
            }else if(c=='{'){
                deque.push('}');
            }else if(c=='['){
                deque.push(']');
                //判断栈顶是否为空       返回栈顶元素 但并不删除
            }else if(deque.isEmpty()||deque.peek()!=c){
                return false;
            }else {
                //移除栈顶元素
                deque.pop();
            }
        }
        //最后判断栈是否为空，如果为空 则代表比较完了，刚刚好
        //如果不为空则代表有一些元素还在里面，
        return deque.isEmpty();
    }
}
